package com.ting.test.algorithms.递归和动态规划.从左往右的模型;

/**
 * 有一个数组，数组中的每一个元素都代表一张货币，数字代表货币的面值，即使是面值相同的元素，也是不同的两张货币
 * 有一个目标金额aim
 * 求出，能够组成目标金额的所有方案
 */
public class 不同面值货币问题1 {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 1, 1, 1, 3, 4, 4, 3, 2, 2, 2, 5, 5, 5};//货币
        int aim = 20;//目标金额
        int count = ways(arr, aim);
    }

    private static int ways(int[] arr, int aim) {
        if (arr == null || aim < 0) {
            return 0;
        }

        // 根据题意  主函数调用，从0位置开始，要求拼装aim元一共有多少种方案
//        return process(arr, 0, aim); 暴力递归方案
        return dp(arr, aim);
    }

    /**
     * @param arr   货币数组
     * @param index 从哪个位置的货币开始
     * @param rest  目标金额
     * @return 返回从index位置的元素开始，要拼装aim的方案个数
     */
    private static int process(int[] arr, int index, int rest) {
        //base case
        if (index == arr.length) {
            //如果货币都已经用完了 恰好rest等于0 则说明当前的方案是可行的，否则不可行
            return rest == 0 ? 1 : 0;
        }
        // 正对当前位置 有两种选择，当前货币要或者不要
        //总的方案个数，应该是这两种情况下方案的总和
        int p1 = process(arr, index + 1, rest);//当前货币不要
        int p2 = process(arr, index + 1, rest - arr[index]);//当前货币要
        return p1 + p2;

    }

    /**
     * @param arr 货币数组
     * @param aim 目标金额
     * @return 返回从index位置的元素开始，要拼装aim的方案个数
     */
    private static int dp(int[] arr, int aim) {
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];//dp数组的每一个元素代表的是在(index,aim) 下的所有方案个数

        //根据process()的base case 可知 当前index==N 且 rest==0时，才能认为是一种方案，返回1  其他都是0
        // 对应到dp数组  只有  dp[N][0]=1;其余都是0，但数组的默认值就是0，因此不需要设置其他
        dp[N][0] = 1;

        //根据process() 我们发现，dp[index]的值总是依赖dpp[index+1]位置的值，且根据上面我们已经求出了dp[N]位置的值，
        //因此我们只需要倒着求就行了
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest < aim; rest++) {
                //rest - arr[index] 有可能小于0 导致数组越界，越界就直接认为没有这种方案，返回0即可
                dp[index][rest] = dp[index + 1][rest] +  ((rest - arr[index]) < 0 ? 0 : dp[index + 1][rest - arr[index]]);;
            }
        }
        return dp[0][aim];

    }
}
